#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cassert>

#ifdef __CUDACC__
  #include <cuda_runtime.h>
#endif

#ifdef _OPENMP
  #include <omp.h>
#endif

using namespace std;

#ifndef BEHCH_MARK_THREADS
  #define BEHCH_MARK_THREADS 16
#endif

#define CHECK(call)                                                           \
{                                                                             \
  const cudaError_t error = call;                                             \
  if (error != cudaSuccess)                                                   \
  {                                                                           \
    printf ("ERROR: %s:%d, ", __FILE__, __LINE__);                            \
    printf ("code: %d, reason: %s\n", error, cudaGetErrorString (error));     \
    exit (1);                                                                 \
  }                                                                           \
}

#define PRODUCTION_MAX 512
#define ITEM_MAX 128
#define VN_MAX 128
#define VT_MAX 128
#define STRING_MAX 1024

/**
 * used to index the sorted productions and items
 * @ptr:    means the subscript of production[] or item[]
 * @length: means the same type size
**/
struct Index
{
  int ptr;
  int size;
  Index (): ptr(-1), size(0) { }
};

/**
 * record production like <0>::=<1><2>
 * @A:  <0>
 * @B:  <1>
 * @C:  <2>
**/
struct Production
{
  int A;
  int B;
  int C;
};

/**
 * record production like <0>::=<1>
 * @A:  <0>
 * @B:  <1>
**/
struct Item
{
  int A;
  char B;
};

// index of Item by item.B
Index i_idx[VT_MAX];

Production production[PRODUCTION_MAX];

Item item[ITEM_MAX];

/**
 * h_dp[i][j][v] = n
 * There are n time of situation for string[i, j] to reduce to v
**/
// unsigned int h_dp[STRING_MAX][STRING_MAX][VN_MAX];
unsigned int h_dp[STRING_MAX * STRING_MAX * VN_MAX];

int vn_num;
int production_num;
int item_num;
int string_length;
char str[STRING_MAX];

__host__ __device__ inline size_t index(const int x, const int y, const int z)
{
  return x * STRING_MAX * VN_MAX + y * VN_MAX + z;
}

__global__ void node(
  unsigned int *d_dp,
  Production *d_production,
  int production_num,
  int string_length,
  int len)
{
  int l = threadIdx.x + threadIdx.y * blockDim.x + threadIdx.z * blockDim.x * blockDim.y;
  int r = l + len - 1 ;
  if (l <= string_length - len)
  {
    for (int mid = l + 1; mid <= r; mid++)
    {
      for (int p = 0; p < production_num; p++)
      {
        d_dp[index(l, r, d_production[p].A)]
          += d_dp[index(l, mid - 1, d_production[p].B)]
          * d_dp[index(mid, r, d_production[p].C)];
      }
    }
  }
}

int main(int argc, char **argv)
{
  omp_set_num_threads (BEHCH_MARK_THREADS);
  // basic io
  if (argc != 2)
  { printf ("cyk <input.txt>"); return 0; }

  freopen(argv[1], "r", stdin);
  scanf("%d\n", &vn_num); scanf("%d\n", &production_num);
  for (int i = 0; i < production_num; i++)
    scanf("<%d>::=<%d><%d>\n", &production[i].A, &production[i].B, &production[i].C);
  scanf("%d\n", &item_num);
  for (int i = 0; i < item_num; i++)
    scanf("<%d>::=%c\n", &item[i].A, &item[i].B);
  scanf("%d\n", &string_length); scanf("%s\n", str);

  // sort ascending order by item.B and item.A
  sort (item, item + item_num, [](const Item& a,
                                  const Item& b)
  { return a.B == b.B ? a.A < b.A : a.B < b.B; });

  // init the index which indexed by [item.B]
  for (int i = 0; i < item_num; i++)
  {
    int t = item[i].B;
    if (i_idx[t].ptr == -1) i_idx[t].ptr = i;
    i_idx[t].size++;
  }

  // compute len is 1 situation
  for (int i = 0; i < string_length; i++)
  {
    int t = str[i];
    for (int j = i_idx[t].ptr; j < i_idx[t].ptr + i_idx[t].size; j++)
      h_dp[index(i, i, item[j].A)] = 1;
  }

  // for cuda
  unsigned int *d_dp;
  Production *d_production;

  CHECK (cudaMalloc (&d_dp, sizeof (h_dp)));
  CHECK (cudaMemcpy (d_dp, h_dp, sizeof (h_dp), cudaMemcpyHostToDevice));
  CHECK (cudaMalloc (&d_production, sizeof (production)));
  CHECK (cudaMemcpy (d_production, production, sizeof (production), cudaMemcpyHostToDevice));

  for (int len = 2; len <= string_length / 2; len++)
  {
    int s = (int)sqrt (string_length - len + 1);
    dim3 block((string_length - len + 1) / s, s + 1);
    // printf ("%d: %d %d %d\n", len, block.x, block.y, block.z);
    node<<<1, block>>> (d_dp, d_production, production_num, string_length, len);
  }

  CHECK (cudaMemcpy (h_dp, d_dp, sizeof (h_dp), cudaMemcpyDeviceToHost));

  CHECK (cudaFree (d_dp));
  CHECK (cudaFree (d_production));
  CHECK (cudaDeviceReset());
  
  for (int len = string_length / 2 + 1; len <= string_length; len++)
  {
    #pragma omp parallel for
    for (int l = 0; l <= string_length - len; l++)
    {
      int r = l + len - 1;
      for (int mid = l + 1; mid <= r; mid++)
      {
        for (int p = 0; p < production_num; p++)
        {
          h_dp[index (l, r, production[p].A)]
            += h_dp[index (l, mid - 1, production[p].B)]
            * h_dp[index (mid, r, production[p].C)];
        }
      }
    }
  }
  
  printf("%u\n", h_dp[index (0, string_length - 1, 0)]);
  return 0;
}
